package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-10-02 15:19
 */

/**
 * 题目：
 * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，
 * 可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，
 * 生成多级数据结构，如下面的示例所示。
 * 给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，
 * 使所有结点出现在单级双链表中。
 */

public class Test41_展平多级双向链表 {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    Node cur = new Node();
    Node ans = cur;

    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        dfs(head);
        ans.next.prev = null;
        return ans.next;
    }

    private void dfs(Node head) {
        if (head == null) {
            return;
        }
        Node child = head.child;
        Node next = head.next;
        cur.next = head;
        cur.next.prev = cur;
        cur = cur.next;
        cur.child = null;
        dfs(child);
        dfs(next);
    }


}
